package Greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class _406_QueueReconstructionbyHeight {
    //hint:first,group people by their height,then sort by the ordinal in every group,last combine all groups from
    //highest to lowest.
    //idea:every group can treat as a exclusive sub-problem,and combine from the top to the bottom can satisfy every
    //group's ask.ep:[7,0],[7,1],no matter how [6,0],[6,1] is inserted,they are satisfied,so only need to satisfy the loeer
    //group's ask.
    public int[][] reconstructQueue(int[][] people) {
        //pick up the tallest guy first
        //when insert the next tall guy, just need to insert him into kth position
        //repeat until all people are inserted into list
        Arrays.sort(people,(a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
        List<int[]> res = new LinkedList<>();
        for(int[] cur : people){
            res.add(cur[1],cur);
//            System.out.println(cur[1]);
//            System.out.println(cur[0]);
//            System.out.println(cur);
        }
        return res.toArray(new int[people.length][]);
    }
}
